package JAVAcollectionsanddatastructures.Stack;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//判断是否为出栈序列
public class StackTest {
    public boolean IsPopOrder(int[] pushA, int[] popB) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popB.length && stack.empty() == false && stack.peek() == popB[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }


//怎么计算一个后缀

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String value = tokens[i];

            //判断是否为整数，是的话就存入栈
            if (isOperation(value) == false) {
                stack.push(Integer.parseInt(value));//转化成整型
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (value) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    //判断是否为运算符
    public boolean isOperation(String x) {
        if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
            return true;
        }
        return false;
    }


    //判断括号是否匹配：栈里面存储左括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {//遇到右括号
                if (stack.empty()) {
                    System.out.println("右括号多");
                    return false;
                } else {
                    char top = stack.peek();
                    if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {
                        stack.pop();
                    } else {
                        System.out.println("括号不匹配");
                        return false;
                    }
                }
            }
            if (!stack.empty()) {
                System.out.println("左括号多");
                return false;
            }
            return true;
        }
        return false;
    }



    //=========两个队列实现栈=================
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public StackTest() {
        this.queue1 = new LinkedList<>();
        this.queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if (queue1.isEmpty() == false) {
            queue1.offer(x);
        } else if (queue2.isEmpty() == false) {
            queue2.offer(x);
        } else {
            queue1.offer(x);//都为空就指定queue1
        }
    }

    //返回栈顶元素并删除
    public int pop() {
        if (empty()) {
            throw new RuntimeException("队列为空");
        }
        if (queue1.isEmpty() == false) {
            int size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                int value = queue1.poll();
                queue2.offer(value);
            }
            return queue1.poll();
        }
        if (queue2.isEmpty() == false) {
            int size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                int value = queue2.poll();
                queue1.offer(value);
            }
            return queue2.poll();//返回并删除
        }
        return -1;
    }

    //返回栈顶元素
    public int top() {
        if (empty()) {
            throw new RuntimeException("队列为空");
        }
        if (queue1.isEmpty() == false) {
            int value = -1;
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                value = queue1.poll();
                queue2.offer(value);
            }
            return value;
        }
        if (queue2.isEmpty() == false) {
            int value = -1;
            int size = queue2.size();
            for (int i = 0; i < size; i++) {
                value = queue2.poll();
                queue1.offer(value);
            }
            return value;//只是返回
        }
        return -1;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
